﻿package level4.grid_case.astar
{
	import level4.grid_case.grid.Grid;
	import level4.grid_case.grid.Node;

	/**
	 * 完成举行网格寻路
	 * */
	public class AStar
	{
		//已考察表
		private var _open:Array;
		//待考察表
		private var _closed:Array;
		//网格
		private var _grid:Grid;
		//终点节点
		private var _endNode:Node;
		//开始节点
		private var _startNode:Node;
		//路径
		private var _path:Array;
		//评价公式
		private var _heuristic:String = PathFormula.MANHATTEN;
		//直接 的消耗
		private var _straightCost:Number = 1.0;
		//斜角的消耗
		private var _diagCost:Number = Math.SQRT2;
		
		public function AStar()
		{
		}
		/**
		寻路 开始
		*/
		public function findPath(grid:Grid):Boolean{
			_grid = grid;
			_open = [];
			_closed = [];
			_startNode = _grid.startNode;
			_endNode = _grid.endNode;
			_startNode.g = 0;
			_startNode.h = PathFormula.calculatePath(heuristic,_startNode,_endNode);
			_startNode.f = _startNode.g+_startNode.h;
			return search();
		}
		private function search():Boolean{
			var node:Node = _startNode;
			while(node != _endNode){
				//获取周围的8个节点
				var startX:int = Math.max(0,node.x -1);
				var endX:int = Math.min(_grid.numCols-1,node.x+1);
				var startY:int = Math.max(0,node.y - 1);
				var endY:int = Math.min(_grid.numRows-1,node.y+1);
				//-------------------------------------------------遍历周围的所有节点,共9个
				for(var i:int = startX; i <= endX;i++){
					for(var j:int = startY;j<= endY;j++){
						var test:Node = _grid.getNode(i,j);
						//交差 不通过
						if(test == node || !test.walkable ||
							!_grid.getNode(node.x,test.y).walkable ||! _grid.getNode(test.x,node.y).walkable){
							continue;
						}
						//首选直接代价
						var cost:Number = _straightCost;
						//若2节点处于对角线处,使用对角线代价
						if(node.x != test.x && node.y != test.y){
							cost = _diagCost;
						}
						//计算从起点到当前点的距离,
						var g:Number = node.g + cost * test.costMultiplier;
						var h:Number = PathFormula.calculatePath(heuristic,test,_endNode);
						var f:Number = g + h;
						//test节点已经存在时,若test的代价>总代价,重置test节点的代价
						if(isOpen(test) || isClosed(test)){
							if(test.f > f){
								test.f = f;
								test.g = g;
								test.h = h;
								test.parent = node;
							}
						}else{
							//计算过的节点,加入到待考察表,稍后进行排序,找出代价最小的节点.
							test.f = f;
							test.g = g;
							test.h = h;
							test.parent = node;
							_open.push(test);
						}
					}
				}
				//---------------------------------------------------周围所有节点遍历结束
				//for(var o:int=0;o<_open.length;o++){}
				//将node加入到已考察表
				_closed.push(node);
				if(_open.length ==0){
					trace("no path");
					return false;
				}
				//将待考察表按总代价(f)来排序,然后取出第一个节点作为下次遍历的起点
				_open.sortOn("f",Array.NUMERIC);
				node = _open.shift() as Node;
			}
			buildPath();
			return true;
		}
		/**
		 * 从 结束节点回溯到开始节点,
		 * */
		private function buildPath():void{
			_path = [];
			var node:Node = _endNode;
			_path.push(node);
			while(node != _startNode){
				node = node.parent;
				_path.unshift(node);
			}
		}
		/**
		 * 节点 是否在open数组内
		 * */
		private function isOpen(node:Node):Boolean{
			for(var i:int=0;i<_open.length;i++){
				if(_open[i] == node){
					return true;
				}
			}
			return false;
		}
		/**
		 * 节点 是否在closed数组内
		 * */
		private function isClosed(node:Node):Boolean{
			for(var i:int=0;i<_closed.length;i++){
				if(_closed[i] == node){
					return true;
				}
			}
			return false;
		}
		/**
		 * 获取 经过的节点
		 * */
		public function get visited():Array{
			return _closed.concat(_open);
		}
		/**
		 * 获取 正确的路径
		 * */
		public function get path():Array{
			return _path;
		}
		///////////////////////////////
		//Getter Setter
		///////////////////////////////
		/**
		 * 设置获取h代价的公式,目前有3种
		 * PathFormula.DIAGONAL
		 * PathFormula.EUCLIDIAN
		 * PathFormula.MANHATTEN
		 * */
		public function get heuristic():String{
			return _heuristic;
		}
		public function set heuristic(value:String):void{
			_heuristic = value;
		}
	}
}